In a digital color imaging system, a color image is represented as a set of color picture elements ("pixels"). Each pixel has associated with it a set of color values which describe the color (hue, saturation and lightness) for that position in the image. The color values correspond to the color coordinates in some given color space. There are many different color spaces (e.g. RGB, CIE tristimulus (XYZ), CIELAB, CIELUV, CMY(K), etc.) which are commonly used. Some color spaces, such as XYZ, CIELAB, and CIELUV are device independent and will therefore give an absolute measure of the color for each pixel in the image. Others, such as RGB and CMY(K), are device dependent and can only be related to an absolute color value if the spectral characteristics of the colorants produced by a specific device are known.
For many applications it is necessary to take color image data from one device having given spectral characteristics and display, manipulate, and/or print it on another device which may have very different spectral characteristics. For this reason, it is often necessary to be able to take image data in one color space, and convert it to a different color space. For example, it may be required to take RGB data from an input scanner and convert it to a device independent space such as CIELAB. This data in the device independent color space Can then be used by a variety of different output devices. The digital image data in the device independent color space is converted to the output device dependent color space for display on the output device. The various devices need to be calibrated so that the image will have the same color appearance regardless of what output device is used. As used herein, the term "calibrate" means to form a color transformation that converts color image data to an output device dependent color space.
To compute color transformations such as this, it is necessary to model the color reproduction characteristics of the input and output devices. For some types of devices, such as computer video displays, the models may involve fairly simple mathematical equations. However, for other devices such as color printers, the behavior may be quite complex and can be best characterized by printing a series of color patches with known input control values, and measuring the color which is produced.
Typically, a regular lattice 10 of device control values (e.g. CMY values) as shown in FIG. 1, is sent to the output device to generate an array of color patches. The color patches are then measured by a colorimeter or spectrophotometer to obtain measured color values. The measured color values will form a new lattice of points 12 in the desired calibration color space (such as CIELAB) as is shown in FIG. 2. The measured data points can then be used to approximate the device response for intermediate control values which were not measured using various interpolation techniques, such as tri-linear interpolation, or convex interpolation as is shown in U.S. patent application Ser. No. 068,823, filed May, 1993 in the names of Shijie J. Wan, Rodney L. Miller and James R. Sullivan for "Method for Convex Interpolation for Color Calibration". The measured data points in combination with an interpolation method as described above are referred to as a "Device Model". Device models like this which convert from the device control signal space (e.g. cyan, magenta, and yellow--CMY) to some device independent color space (such as CIELAB) are referred to herein as "forward models". The volume enclosed by the lattice of points 12 in FIG. 2 represents the colors which can be reproduced on the device, and is referred to as the color gamut of the device. The term gamut boundary refers to the surface of this color gamut volume.
Device models which compute the device control signals necessary to produce some particular device independent color value are often referred to as "inverse models". For 3-color devices, there is generally a one-to-one mapping between colors in the device control signal space, and colors in the device independent (output) color space. As a result it is possible to uniquely determine an inverse model for some device for colors which are inside the gamut of printable colors. Various inverse interpolation techniques have been developed to compute inverse models for 3-color devices from the measured device characteristics. One common method is to break each "cube" 14 in the lattice of input control values for the measured data up into six tetrahedrons 16. One common geometry used to form the tetrahedrons is shown in FIG. 3. Corresponding tetrahedrons are also formed in the lattice of output color values. A list of these tetrahedra are stored in a data structure containing the input and output color values corresponding to each corner of the tetrahedra. To determine the inverse mapping for a given output color, the data structure is searched for the tetrahedron in the output color space which contains the specified output color. The corresponding input color value can then be determined by interpolating between the input color values for the corresponding tetrahedron in the input control value space. Since the search process involved with this method can be somewhat time-consuming, it is often desirable to use this technique to determine the inverse mapping for a regular lattice of color values in the output color space to form an inverse Look-up Table (LUT). Simpler interpolation techniques, such as tri-linear interpolation, can then be used to process large numbers of image pixels through the inverse LUT quickly.
For four-color (e.g. cyan, magenta, yellow and black-CMYK) output devices, the problem of determining an inverse LUT is complicated due to the fact that many sets of input control values may map to a single output color. FIG. 4 shows a typical color gamut 18 of a 4-color device for several different black levels. The total color gamut comprises a plurality of gamut volumes, one for each black level. For example, the gamut volume 20 represents no black, the volume 22 represents 50% black, and the volume 24 represents full black. The vertices of the no black gamut volume are labeled with the initial of the subtractive primary color(s) C,M,Y that produced the color value at the vertex.
Each of the gamut volumes is similar to the color gamut of a 3-color device, and is generated by holding the black level constant and varying the cyan, magenta, and yellow colorant levels over their full range. Although, only 3 black levels are shown in this figure, there will usually be 256 or more black levels available to the device. The union of the color gamut volumes for all of the available black levels will represent the overall color gamut 18 of the device.
FIG. 5 shows the overall color gamut 18 for the example given in FIG. 4 where the vertices are labeled by the primary color C,M,Y,K or combination thereof that produced the color value at the vertex. Colors on the surface of the gamut can only be reproduced with a unique combination of CMYK colorant levels, but colors in the interior of the gamut can be reproduced using a variety of CMYK combinations corresponding to different black levels. There is therefore no unique solution to the inverse problem where it is desired to find the colorant levels necessary to produce a given output color. A number of methods have been developed to determine appropriate combinations of colorant levels to produce the desired output color value. Generically, these methods are referred to as "black strategies". In the graphic arts field, they are also known as gray-component removal (GCR) or under color removal (UCR) methods. The methods vary widely in speed, accuracy, and complexity and represent various trade-offs between these properties. Typical examples of these methods include interactive search techniques, global polynomial fits of measured device data, and empirical relationships which involve computing CMY colorant levels for a 3-color device and replacing some of the colorants with black when all three colorants are present.
The basis of many black component strategies for 4-color printers is the determination of the minimum and/or maximum black levels which can be used to produce the desired output color. Most prior art methods for determining these values are either iterative in nature and as a result computationally slow, or involve a polynomial fit or some other type of approximation to the known device characteristics.
Thus it can be seen that there is presently a need for a new calibration method for 4-color CMYK devices which is simultaneously fast, simple, accurate, and supports a variety of black strategies.